//
// Created by lwj12 on 24-7-30.
//
#include "Sort.h"
#include "Stack.h"

void Swap(int* a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void PrintArray(int* a, size_t sz)
{
    for (size_t i = 0; i < sz; ++i)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}

void InsertSort(int* a, size_t sz)
{
     int end, tmp;
     for(int i = 1; i < sz; i++)
    {
         end = i - 1;
         tmp = a[i];
         while (end >= 0 && tmp < a[end])
         {
             a[end + 1] = a[end];
             end--;
         }
         a[end + 1] = tmp;
    }
}

void BubbleSort(int* a, size_t sz)
{
    int tmp, flag;
    for (size_t i = sz - 1; i > 0 ; i--)
    {
        flag = 1;
        for(int j = 0; j < i; j++)
        {
            if(a[j] > a[j + 1])
            {
                Swap(&a[j], &a[j + 1]);
                flag = 0;
            }
        }
        if(flag) break;
    }
}

void ShellSort(int* a, size_t sz)
{
    for(int gap = (int)(sz / 3) + 1; gap > 0; gap /= 2)
    {
        int end, tmp;
       for(int i = gap; i < sz; i++)
        {
           end = i;
           tmp = a[i];
           while (end >= gap && tmp < a[end - gap])
           {
               a[end] = a[end - gap];
               end -= gap;
           }
           a[end] = tmp;
       }
    }
}

void SelectSort(int* a, size_t sz)
{
    int begin = 0, end = (int)sz - 1;
    int mini, maxi;
    while (end > begin)
    {
        mini = maxi = begin;
        for(int i = begin; i <= end; i++)
        {
            if(a[i] < a[mini]) mini = i;
            if(a[i] > a[maxi]) maxi = i;
        }
        Swap(&a[mini], &a[begin]);
        if(maxi == begin) maxi = mini;
        Swap(&a[maxi], &a[end]);
        begin++, end--;
        PrintArray(a, sz);
    }
}

//霍尔
/*void QuickSort(int* a, int begin, int end)
{
    if(begin >= end) return;
    int key =a[begin], left = begin, right = end;
    while (left < right)
    {
        while (a[right] > key ) right--;
        while (a[left] <= key && left < right) left++;
        if(left < right) Swap(&a[left], &a[right]);
    }
    Swap(&a[begin], &a[left]);
    QuickSort(a, begin, right - 1);
    QuickSort(a, left + 1, end);
}*/

int getMedian(int* a, int left, int right)
{
    int mid = left + (right - left) / 2;
    if(a[left] > a[right])
    {
        if(a[mid] > a[left]) return left;
        else if(a[right] > a[mid]) return right;
        else return mid;
    }
    else
    {
        if(a[mid] > a[right]) return right;
        else if(a[left] > a[mid]) return left;
        else return mid;
    }
}

//快慢指针法
void QuickSort(int* a, int begin, int end)
{
    if(begin >= end) return;
    //基础版本
    //int keyi = begin;

    //随机值法
    //int keyi = rand() % (end - begin + 1) + begin;

    //三数取中
    int keyi = getMedian(a, begin, end);
    Swap(&a[keyi], &a[begin]);
    keyi = begin;

    int prev = begin, cur = begin + 1;
    while (cur <= end)
    {
        if(a[cur] < a[keyi] && ++prev != cur) Swap(&a[cur], &a[prev]);
        cur++;
    }
    Swap(&a[keyi], &a[prev]);
    keyi = prev;
    QuickSort(a, begin, keyi - 1);
    QuickSort(a, keyi + 1, end);
}

//非递归(迭代)
void quickSortIterative(int* a, int begin, int end)
{
    Stack st;
    STInit(&st);
    Scope sc;
    sc.left = begin, sc.right = end;
    STPush(&st, sc);
    while (! isEmpty(&st))
    {
        sc = STTop(&st);
        int left = sc.left, right = sc.right;
        int keyi = getMedian(a, left, right);
        Swap(&a[keyi], &a[left]);
        keyi = left;

        int prev = left, cur = left + 1;
        while (cur <= right)
        {
            if(a[cur] < a[keyi] && ++prev != cur) Swap(&a[cur], &a[prev]);
            cur++;
        }
        Swap(&a[keyi], &a[prev]);
        keyi = prev;
        STPop(&st);
        if(keyi - 1 > left)
        {
            sc.right = keyi - 1;
            STPush(&st, sc);
        }
        if(keyi + 1 < right)
        {
            sc.left = keyi + 1;
            sc.right = right;
            STPush(&st, sc);
        }
    }
    STDestroy(&st);
}


void _MergeSort(int* a, int begin, int end, int* tmp)
{
    if(begin >= end) return;
    int mid = begin + (end - begin) / 2;

    _MergeSort(a, begin, mid, tmp);
    _MergeSort(a, mid +1, end, tmp);

    int begin1 = begin, end1 = mid;
    int begin2 = mid + 1, end2 = end;
    int i = 0;
    while (begin1 <= end1 && begin2 <= end2)
    {
        if(a[begin1] > a[begin2]) tmp[i++] = a[begin2++];
        else tmp[i++] = a[begin1++];
    }
    while (begin1 <= end1) tmp[i++] = a[begin1++];
    while (begin2 <= end2) tmp[i++] = a[begin2++];
    memcpy(a + begin, tmp, (end - begin + 1) * sizeof (int));
}

void MergeSort(int* a, size_t sz)
{
    int* tmp = (int*)malloc(sz * sizeof (int));
    if(tmp == NULL)
    {
        perror("MergeSort malloc fail");
        return;
    }
    _MergeSort(a, 0, sz - 1, tmp);
    free(tmp);
    tmp = NULL;
}

void MergeSortIterative(int* a, size_t sz)
{
    int* tmp = (int*)malloc(sz * sizeof (int));
    if(tmp == NULL)
    {
        perror("MergeSort malloc fail");
        return;
    }
    int begin1, end1, begin2, end2, i;
    for (int gap = 1; gap < sz ; gap *= 2)
    {
        for (int j = 0; j < sz; j += gap * 2)
        {
            if(j + gap >= sz) continue;
            begin1 = j, end1 = j + gap - 1;
            begin2 = end1 + 1, end2 = begin2 + gap - 1 > sz - 1 ? sz - 1 : begin2 + gap - 1;
            i = 0;
            while (begin1 <= end1 && begin2 <= end2)
            {
                if(a[begin1] > a[begin2]) tmp[i++] = a[begin2++];
                else tmp[i++] = a[begin1++];
            }
            while (begin1 <= end1) tmp[i++] = a[begin1++];
            while (begin2 <= end2) tmp[i++] = a[begin2++];
            memcpy(a + j, tmp, (end2 - j + 1) * sizeof (int));
        }
    }
    free(tmp);
    tmp = NULL;
}

void AdjustDown(int* a, int father, int root)
{
    int child = 2 * father + 1;
    while (child <= root)
    {
        if(child + 1 <= root && a[child] < a[child + 1]) child++;
        if(a[father] < a[child]) Swap(&a[father], &a[child]);
        father = child;
        child = 2 * father + 1;
    }
}

void HeapSort(int* a, size_t sz)
{
    for(int i = (sz - 2) / 2; i >= 0; i--) AdjustDown(a, i, sz - 1);
    int i = sz - 2;
    while (i--)
    {
        Swap(&a[0], &a[i + 2]);
        AdjustDown(a, 0, i + 1);
    }
}

void CountSort(int* a, size_t sz)
{
    int max = a[0], min = a[0];
    for(int i = 1; i < sz; i++)
    {
        if(a[i] > max) max = a[i];
        if(a[i] < min) min = a[i];
    }
    int range = max - min + 1;
    int* count = (int*)malloc(range * sizeof(int));
    if(count == NULL)
    {
        perror("CountSort malloc fail");
        return;
    }
    memset(count, 0, range * sizeof (int));
    for (int i = 0; i < sz; ++i)  count[a[i] - min]++;
    int j = 0;
    for(int i = 0; i < range; i++)  while (count[i]--)  a[j++] = i + min;
}